package demo_0712;

public class T7_0328 {
    //给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

    private int postIndex;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postIndex = postorder.length - 1;
        return buildChild(postorder,inorder,0,inorder.length - 1);
    }
    //后序遍历：左右根
    //中序遍历：左根右
    //后序遍历的最后一个元素一定是根节点，所以先找到根节点，再在中序遍历中找到根节点的位置，根节点的左边就是左子树，右边就是右子树，然后递归构建左子树和右子树。
    // 1. 找到根节点
    // 2. 找到根节点在中序遍历中的位置
    // 3. 递归构建左子树和右子树
    // 4. 返回根节点
    private TreeNode buildChild(int[] postorder,int[] inorder, int inbegin, int inend) {
        //如果inbegin > inend，说明没有节点了，返回null
        if (inbegin > inend) return null;
        TreeNode root = new TreeNode(postorder[postIndex]);
        int rootIndex = findIndex(inorder,inbegin,inend,postorder[postIndex]);
        //如果rootIndex == -1，说明没有根节点，返回null
        if (rootIndex == -1) return null;
        postIndex--;
        //先构建右子树，因为后序遍历的顺序是左右根，所以先构建右子树，再构建左子树
        // 为什么要先构建右子树呢？因为后序遍历的顺序是左右根，所以先构建右子树，再构建左子树，这样才能保证根节点的左右子树都构建好了，才能返回根节点。
        //如果先构建左子树，那么根节点的右子树还没有构建好，就返回根节点了，这样就会出错。
        root.right = buildChild(postorder,inorder,rootIndex+1,inend);
        root.left = buildChild(postorder,inorder,inbegin,rootIndex-1);
        return root;
    }

    private int findIndex(int[] inorder, int inbegin, int inend, int key) {
        for (int i = inbegin; i <= inend; i++) {
            if (inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }
}
